public class Leetcode {
}

//leetcode:面试题17.16.按摩师
class Solution1 {
    public int massage(int[] nums) {
        int n = nums.length;
        if( n == 0) return 0;

        //设立两个数组数组f代表这个位置处于接的状态
        int[] f = new int[n];
        //g数组代表这个位置处于不接的状态
        int[] g = new int[n];

        //如果第一位置是接取状态，就将它这个位置的值设为nums[0]
        f[0] = nums[0];
        for(int i = 1; i < n; i++){
            //如果处于接取状态，那么这个位置的前一个位置必定处于未接的状态
            //所以这个位置的值为g[i-1]+nums[i]
            f[i] = g[i-1] + nums[i];
            //如果这个位置处于未接状态那么，他的前一个位置可以为接取和未接取的状态
            //而此时的最长时间就为他俩的最大值
            g[i] = Math.max(f[i-1],g[i-1]);
        }
        //那么我们这整个数组的最大时间就为，最后一次是接或不接的最大值
        return Math.max(f[n-1],g[n-1]);
    }
}

//leetcode:198:打家劫舍
//此题跟上题是一个意思相同的解法
class Solution2 {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;

        int[] f = new int[n];
        int[] g = new int[n];

        f[0] = nums[0];
        for(int i = 1; i < n; i++){
            f[i] = g[i-1] + nums[i];
            g[i] = Math.max(g[i-1],f[i-1]);
        }
        return Math.max(f[n-1],g[n-1]);
    }
}

//leetcode:213:打家劫舍II
class Solution3 {
    public int rob(int[] nums) {
        int n = nums.length;
        //如果从第0个开始偷，那么就下一个要偷的房间就为第2个，同时最后一个不能偷，所以就相当于是从2~n-2位置做一次打家劫舍1.
        //如果我们从第1个位置开始偷，此时最后一个位置就可以偷，就相当于是从1~n-1位置做一次打家劫舍1
        //最后返回这两种方式的最大值
        return Math.max(nums[0] + robRange(nums,2,n-2), robRange(nums,1,n-1));
    }

    public int robRange(int[] nums, int left , int right){
        if(left > right) return 0;
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];

        f[left] = nums[left];
        for(int i = left + 1; i <= right; i++){
            f[i] = g[i-1] + nums[i];
            g[i] = Math.max(f[i-1],g[i-1]);
        }
        return Math.max(f[right],g[right]);
    }
}